package problem95_UniqueBinarySearchTreesII;

import java.util.ArrayList;
import java.util.List;

import problem108_Convert_Sorted_Array_to_Binary_Search_Tree.TreeNode;

public class SolutionUsingDP {
	@SuppressWarnings("unchecked")
	public List<TreeNode> generateTrees(int n) {
		List<?>[] dp = new List<?>[n + 1];
		dp[0] = new ArrayList<TreeNode>();
		if(n==0)	return (List<TreeNode>) dp[0];
		dp[0].add(null);
		for (int i = 1; i <= n; i++) {
			dp[i] = new ArrayList<TreeNode>();
			for (int j = 0; j < i; j++) {
				List<TreeNode> leftSubTrees = (List<TreeNode>) dp[j];
				List<TreeNode> rightSubTrees = (List<TreeNode>) dp[i - j - 1];
				for (TreeNode left : leftSubTrees) {
					for (TreeNode right : rightSubTrees) {
						TreeNode root = new TreeNode(j + 1);
						root.left = left;
						root.right = clone(right, j + 1);
						((List<TreeNode>) dp[i]).add(root);
					}
				}
			}
		}
		return (List<TreeNode>) dp[n];
	}

	private TreeNode clone(TreeNode node, int offset) {
		if (node == null)
			return null;
		TreeNode root = new TreeNode(node.val + offset);
		root.left = clone(node.left, offset);
		root.right = clone(node.right, offset);
		return root;
	}
}
